class Solution {
public:
    int search(vector<int>& nums, int target) 
    {
        int left = 0, right = nums.size() - 1;

        while(left <= right)
        {
            int mid = left + (right - left + 1) / 2;//防溢出

            if(nums[mid] > target)
                right = mid - 1;
            else if(nums[mid] < target)
                left = mid + 1;
            else 
                return mid;
        }
        return -1;
    }
};

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) 
    {
        if(stones.size() == 1) 
            return stones[0];
        priority_queue<int> heap;

        for(int n : stones)
            heap.push(n);

        while(heap.size() > 1)
        {
            int x = heap.top();
            heap.pop();
            if(heap.size() > 0)
            {
                int y = heap.top();
                heap.pop();

                if(x != y)
                {
                    heap.push(x - y);
                }
                else 
                {
                    heap.push(0);
                }
            }
        }
        return heap.top();
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        //递归出口
        if(list1 == nullptr)
            return list2;
        if(list2 == nullptr)
            return list1;
        
        if(list1->val <= list2->val)
        {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else
        {
            list2->next =  mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) 
    {
        if(head == nullptr || head->next == nullptr)
            return head;

        ListNode* ret = head->next;
        ret->next = swapPairs(ret->next);
        ListNode* tmp = ret->next;
        ret->next = head;
        head->next = tmp;

        return ret;

    }

};
